#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
		int sum_k = 0;
		for (int i = 0; i < k; i++)
			sum_k += nums[i];
		vector<int> partial;
		for (int i = 0, len = nums.size(); i < len - k; i++) {
			partial.emplace_back(sum_k);
			sum_k -= nums[i];
			sum_k += nums[i + k];
		}
        partial.emplace_back(sum_k);

		vector<int> pre_max(partial.size()); pre_max[0] = 0;
		for (int i = 1, max_idx = 0, len = partial.size(); i < len; i++) {
			if (partial[i] > partial[max_idx]) max_idx = i;
			pre_max[i] = max_idx;
		}

		vector<int> after_max(partial.size()); after_max[after_max.size() - 1] = after_max.size() - 1;
		for (int i = after_max.size() - 2, max_idx = i + 1; i >= 0; i--) {
			if (partial[i] >= partial[max_idx]) max_idx = i;
			after_max[i] = max_idx;
		}

		vector<int> res(3);
		for (int i = k, len = partial.size(), max = 0; i < len - k; i++) {
			int val = partial[i] + partial[pre_max[i - k]] + partial[after_max[i + k]];
			if (val > max) {
				max = val;
				res = {pre_max[i - k], i, after_max[i + k]};
			}
		}

		return res;
	}

private:
};

int main()
{
	Solution solution;
	return 0;
}
